package dp;

//The demons had captured the princess (P) and imprisoned her in the bottom-right corner of a dungeon.
//The dungeon consists of M x N rooms laid out in a 2D grid. Our valiant knight (K) was initially positioned 
//in the top-left room and must fight his way through the dungeon to rescue the princess.
//
//The knight(骑士)has an initial health point represented by a positive integer. 
//If at any point his health point drops to 0 or below, he dies immediately.
//
//Some of the rooms are guarded by demons, so the knight loses health (negative integers) upon entering these rooms;
//other rooms are either empty (0's) or contain magic orbs that increase the knight's health (positive integers).
//
//In order to reach the princess as quickly as possible, the knight decides to move only rightward or downward 
//in each step.

//加了限制条件的dp

//原题：https://leetcode.com/problems/dungeon-game/
public class DungeonGame {

	public static void main(String[] args) {
//		int[][] dungeon = new int[][]{  {-2, -3, 3},
//										{-5, -10, 1},
//										{10, 30, -5}};
		int[][] dungeon = new int[][]{{0, -3}};
		DungeonGame game = new DungeonGame();
		System.out.println("result: " + game.calculateMinimumHP(dungeon));
			
	}
	
	//when we arrival the bottom-right position, the least HP is 1
	//and then we can 逆着推理
	
	//dp[i][j] 表示array[i][j] 的最小HP
	//dp[i][j] = min{Math.max(1, dp[i + 1][j] - array[i + 1][j]), Math.max(1, dp[i][j + 1] - array[i][j + 1])} 
	public int calculateMinimumHP(int[][] dungeon) {
		if(dungeon == null || dungeon.length == 0){
			return -1;
		}
		int m = dungeon.length;
		int n = dungeon[0].length;
		int[][] res = new int[m][n];
		res[m - 1][n - 1] = 1;
		for(int i = m - 2; i >= 0; i--){
			res[i][n - 1] = Math.max(1, res[i + 1][n - 1] - dungeon[i + 1][n - 1]);
		}
		for(int j = n - 2; j >= 0; j--){
			res[m - 1][j] = Math.max(1, res[m - 1][j + 1] - dungeon[m - 1][j + 1]);
		}
		
		for (int i = m - 2; i >= 0; i--) {
			for (int j = n - 2; j >= 0; j--) {
				res[i][j] = Math.min(Math.max(1, res[i + 1][j] - dungeon[i + 1][j]), 
						Math.max(1, res[i][j + 1] - dungeon[i][j + 1]));
			}
		}
		for (int i = 0; i < res.length; i++) {
			for (int j = 0; j < res[0].length; j++) {
				System.out.print(res[i][j] + " ");
			}
			System.out.println();
		}
		return Math.max(1, res[0][0] - dungeon[0][0]);
	}
}
